// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <stdint.h>

#include <string>

#include "base/strings/stringprintf.h"
#include "media/base/test_random.h"
#include "media/blink/interval_map.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace {

// Our tests only modifiy the interval map entries in [0..kTestSize).
// We need this to be big enough to hit tricky corner cases, but small
// enough that we get lots of entry duplication to clean up.
// Also, SimpleIntervalMap uses a vector of size kTestSize to emulate
// a intervalmap, so making this too big will the test down a lot.
const int kTestSize = 16;

class SimpleIntervalMap {
public:
    SimpleIntervalMap()
        : data_(kTestSize)
    {
    }

    void IncrementInterval(int32_t from, int32_t to, int32_t how_much)
    {
        for (int32_t i = from; i < to; i++) {
            data_[i] += how_much;
        }
    }

    void SetInterval(int32_t from, int32_t to, int32_t how_much)
    {
        for (int32_t i = from; i < to; i++) {
            data_[i] = how_much;
        }
    }

    int32_t operator[](int32_t index) const { return data_[index]; }

private:
    std::vector<int32_t> data_;
};

class IntervalMapTest : public testing::Test {
public:
    IntervalMapTest()
        : rnd_(42)
    {
    }
    void IncrementInterval(int32_t from, int32_t to, int32_t how_much)
    {
        truth_.IncrementInterval(from, to, how_much);
        testee_.IncrementInterval(from, to, how_much);
        std::string message = base::StringPrintf("After [%d - %d) += %d", from, to, how_much);
        Compare(message);
    }

    void SetInterval(int32_t from, int32_t to, int32_t how_much)
    {
        truth_.SetInterval(from, to, how_much);
        testee_.SetInterval(from, to, how_much);
        std::string message = base::StringPrintf("After [%d - %d) += %d", from, to, how_much);
        Compare(message);
    }

    // Will exercise operator[] and IntervalMap::const_iterator.
    void Compare(const std::string& message)
    {
        bool had_fail = HasFailure();
        for (int i = 0; i < kTestSize; i++) {
            EXPECT_EQ(truth_[i], testee_[i]) << " i = " << i << " " << message;
        }
        EXPECT_EQ(testee_[-1], 0) << message;
        EXPECT_EQ(testee_[kTestSize], 0) << message;
        int32_t prev_ = 0;
        int32_t end_of_last_interval = 0;
        int32_t num_intervals = 0;
        for (const auto& r : testee_) {
            num_intervals++;
            EXPECT_LT(r.first.begin, r.first.end);
            if (r.first.begin == std::numeric_limits<int32_t>::min()) {
                EXPECT_EQ(0, r.second);
            } else {
                EXPECT_EQ(end_of_last_interval, r.first.begin);
                EXPECT_GE(r.first.begin, 0) << message;
                EXPECT_LE(r.first.begin, kTestSize) << message;
                EXPECT_NE(r.second, prev_) << message;
            }
            end_of_last_interval = r.first.end;
            prev_ = r.second;
        }
        EXPECT_EQ(prev_, 0) << message;

        if (HasFailure() && !had_fail) {
            for (int i = 0; i < kTestSize; i++) {
                LOG(ERROR) << i << ": Truth =" << truth_[i]
                           << " Testee = " << testee_[i];
            }
            for (const auto& r : testee_) {
                LOG(ERROR) << "Interval:  " << r.first.begin << " - " << r.first.end
                           << " = " << r.second;
            }
        }
    }

    void Clear()
    {
        for (int j = 0; j < kTestSize; j++) {
            IncrementInterval(j, j + 1, -truth_[j]);
        }
    }

protected:
    media::TestRandom rnd_;
    SimpleIntervalMap truth_;
    media::IntervalMap<int32_t, int32_t> testee_;
};
}

TEST_F(IntervalMapTest, SimpleTest)
{
    IncrementInterval(3, 7, 4);
    EXPECT_EQ(0, testee_[0]);
    EXPECT_EQ(0, testee_[2]);
    EXPECT_EQ(4, testee_[3]);
    EXPECT_EQ(4, testee_[5]);
    EXPECT_EQ(4, testee_[6]);
    EXPECT_EQ(0, testee_[7]);
    IncrementInterval(3, 7, -4);
    EXPECT_TRUE(testee_.empty());
}

TEST_F(IntervalMapTest, SimpleIncrementTest)
{
    IncrementInterval(3, 7, 1);
    IncrementInterval(6, 10, 2);
    EXPECT_EQ(0, testee_[2]);
    EXPECT_EQ(1, testee_[3]);
    EXPECT_EQ(1, testee_[5]);
    EXPECT_EQ(3, testee_[6]);
    EXPECT_EQ(2, testee_[7]);
    EXPECT_EQ(2, testee_[9]);
    EXPECT_EQ(0, testee_[10]);
    SetInterval(3, 12, 0);
    EXPECT_TRUE(testee_.empty());
}

TEST_F(IntervalMapTest, IncrementJoinIntervalsTest)
{
    IncrementInterval(3, 5, 1);
    IncrementInterval(7, 8, 1);
    IncrementInterval(9, 11, 1);
    IncrementInterval(5, 7, 1);
    IncrementInterval(8, 9, 1);
    auto i = testee_.find(5);
    EXPECT_EQ(3, i.interval_begin());
    EXPECT_EQ(11, i.interval_end());
    EXPECT_EQ(1, i.value());
}

TEST_F(IntervalMapTest, SetJoinIntervalsTest)
{
    SetInterval(3, 5, 1);
    SetInterval(7, 8, 1);
    SetInterval(9, 11, 1);
    SetInterval(5, 9, 1); // overwrites one interval
    auto i = testee_.find(5);
    EXPECT_EQ(3, i.interval_begin());
    EXPECT_EQ(11, i.interval_end());
    EXPECT_EQ(1, i.value());
}

TEST_F(IntervalMapTest, FindTest)
{
    IncrementInterval(5, 6, 1);
    IncrementInterval(1, 10, 2);
    int32_t min_value = std::numeric_limits<int32_t>::min();
    int32_t max_value = std::numeric_limits<int32_t>::max();
    auto i = testee_.find(0);
    EXPECT_EQ(min_value, i.interval_begin());
    EXPECT_EQ(1, i.interval_end());
    EXPECT_EQ(0, i.value());
    i = testee_.find(4);
    EXPECT_EQ(1, i.interval_begin());
    EXPECT_EQ(5, i.interval_end());
    EXPECT_EQ(2, i.value());
    i = testee_.find(5);
    EXPECT_EQ(5, i.interval_begin());
    EXPECT_EQ(6, i.interval_end());
    EXPECT_EQ(3, i.value());
    i = testee_.find(6);
    EXPECT_EQ(6, i.interval_begin());
    EXPECT_EQ(10, i.interval_end());
    EXPECT_EQ(2, i.value());
    i = testee_.find(9);
    EXPECT_EQ(6, i.interval_begin());
    EXPECT_EQ(10, i.interval_end());
    EXPECT_EQ(2, i.value());
    i = testee_.find(10);
    EXPECT_EQ(10, i.interval_begin());
    EXPECT_EQ(max_value, i.interval_end());
    EXPECT_EQ(0, i.value());
}

TEST_F(IntervalMapTest, MinMaxInt)
{
    int32_t min_value = std::numeric_limits<int32_t>::min();
    int32_t max_value = std::numeric_limits<int32_t>::max();

    // Change a single value at minint
    testee_.IncrementInterval(min_value, min_value + 1, 7);
    EXPECT_EQ(7, testee_[min_value]);
    EXPECT_EQ(0, testee_[min_value + 1]);
    auto i = testee_.find(0);
    EXPECT_EQ(min_value + 1, i.interval_begin());
    EXPECT_EQ(max_value, i.interval_end());
    EXPECT_EQ(0, i.value());
    --i;
    EXPECT_TRUE(i == testee_.find(min_value));
    EXPECT_EQ(min_value, i.interval_begin());
    EXPECT_EQ(min_value + 1, i.interval_end());
    EXPECT_EQ(7, i.value());
    testee_.clear();

    // Change a single value at maxint
    // Note that we don't actually have a way to represent a range
    // that includes maxint as the end of the interval is non-inclusive.
    testee_.IncrementInterval(max_value - 1, max_value, 7);
    EXPECT_EQ(7, testee_[max_value - 1]);
    EXPECT_EQ(0, testee_[max_value - 2]);
    i = testee_.find(0);
    EXPECT_EQ(min_value, i.interval_begin());
    EXPECT_EQ(max_value - 1, i.interval_end());
    EXPECT_EQ(0, i.value());
    ++i;
    EXPECT_TRUE(i == testee_.find(max_value - 1));
    EXPECT_EQ(max_value - 1, i.interval_begin());
    EXPECT_EQ(max_value, i.interval_end());
    EXPECT_EQ(7, i.value());

    testee_.clear();

    // Change entire range (almost)
    testee_.IncrementInterval(min_value, max_value, 17);
    EXPECT_EQ(17, testee_[min_value]);
    EXPECT_EQ(17, testee_[0]);
    EXPECT_EQ(17, testee_[max_value - 1]);
    i = testee_.find(0);
    EXPECT_EQ(min_value, i.interval_begin());
    EXPECT_EQ(max_value, i.interval_end());
    EXPECT_EQ(17, i.value());
    EXPECT_TRUE(i == testee_.find(max_value - 1));
    EXPECT_TRUE(i == testee_.find(min_value));
}

TEST_F(IntervalMapTest, RandomIncrementTest)
{
    for (int j = 0; j < 200; j++) {
        Clear();
        for (int i = 0; i < 200; i++) {
            int32_t begin = rnd_.Rand() % (kTestSize - 1);
            int32_t end = begin + 1 + rnd_.Rand() % (kTestSize - begin - 1);
            IncrementInterval(begin, end, (rnd_.Rand() & 32) ? 1 : -1);
            if (HasFailure()) {
                return;
            }
        }
    }
}

TEST_F(IntervalMapTest, RandomSetTest)
{
    for (int j = 0; j < 200; j++) {
        Clear();
        for (int i = 0; i < 200; i++) {
            int32_t begin = rnd_.Rand() % (kTestSize - 1);
            int32_t end = begin + 1 + rnd_.Rand() % (kTestSize - begin - 1);
            SetInterval(begin, end, rnd_.Rand() & 3);
            if (HasFailure()) {
                return;
            }
        }
    }
}
